using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.ComponentModel;
using System.Threading;

namespace BigNumber
{
  

  public enum FactorMode { None, Simple, Full };

  class FactorsHashtable
  {
    private Dictionary<FastBigNumber,int> m_InnerTable;

    public FactorsHashtable()
    {
      m_InnerTable = new Dictionary<FastBigNumber, int>();
    }

    public void AddOne(FastBigNumber key)
    {
      Add(key, 1);
    }

    public void Add(FastBigNumber key, int value)
    {
      if (m_InnerTable.ContainsKey(key))
        m_InnerTable[key] = (m_InnerTable[key]) +  value;
      else
        m_InnerTable.Add(key, value);
    }

    public void Clear()
    {
      m_InnerTable.Clear();
    }

    public int this[FastBigNumber key]
    {
      get
      {
        return m_InnerTable[key];
      }
    }

    public Dictionary<FastBigNumber,int>.KeyCollection Keys
    {
      get
      {
        return m_InnerTable.Keys;
      }
    }

    public bool ContainsKey(FastBigNumber key)
    {
      return m_InnerTable.ContainsKey(key);
    }

    /// <summary>
    /// Adds the factors from other table to this table
    /// </summary>
    /// <param name="otherTable"></param>
    public void Unify(FactorsHashtable otherTable)
    {
      foreach (FastBigNumber key in otherTable.Keys)
      {
        Add(key, otherTable[key]);
      }
    }

    public StdBigNumber ToStdBigNumber
    {
      get
      {
        return ToFastBigNumber.ToStdBigNumber;
      }
    }

    public FastBigNumber ToFastBigNumber
    {
      get
      {
        FastBigNumber result = new FastBigNumber("1");
        foreach (FastBigNumber key in m_InnerTable.Keys)
        {
          int count = (int)m_InnerTable[key];
          result = result * BigNumberMath.Power<FastBigNumber>(key, count);
        }
        return result;
      }
    }

    public override string ToString()
    {
      return ToFastBigNumber.ToString();
    }

    /// <summary>
    /// Gets the total number of factors for the number
    /// </summary>
    public int KnownFactorsCount
    {
      get
      {
        int result = 0;
        foreach (FastBigNumber key in m_InnerTable.Keys)
        {
          result += m_InnerTable[key];
        }
        return result;
      }


    }

  }

  public class FactoringBigNumber : IIntegerBigNumber, IComparable<FactoringBigNumber>
  {
    private FactorsHashtable m_PrimeFactors;
    //private FactorsHashtable m_NonPrimeFactors;
    private FastBigNumber m_Remainder;
    private FactorMode m_FactorMode;
    private bool m_IsNegative;

    private object m_FactoringLock = new object();

    #region Helper Functions

    /// <summary>
    /// Tries to factor the number by using division signs for the primes 2,3,5,7 and 11
    /// </summary>
    /// <param name="number">The number to factor</param>
    /// <param name="remainder">The remaining number after the small factors were removed</param>
    /// <returns></returns>
    private void CreateSimpleFactorization(FastBigNumber number)
    {
      StdBigNumber tempNumber = new StdBigNumber(number.ToString());

      m_PrimeFactors = new FactorsHashtable();
      StdBigNumber two = new StdBigNumber("2");
      StdBigNumber five = new StdBigNumber("5");
      StdBigNumber three = new StdBigNumber("3");
      StdBigNumber seven = new StdBigNumber("7");
      StdBigNumber eleven = new StdBigNumber("11");
      FastBigNumber ftwo = new FastBigNumber("2");
      FastBigNumber ffive = new FastBigNumber("5");
      FastBigNumber fthree = new FastBigNumber("3");
      FastBigNumber fseven = new FastBigNumber("7");
      FastBigNumber feleven = new FastBigNumber("11");

      if (tempNumber.IsZero)
      {
        m_Remainder = 0;
        return;
      }
      while (!tempNumber.IsOne) 
      {
        if (tempNumber.IsDivisibleByTwo)
        {
          m_PrimeFactors.AddOne(ftwo);
          tempNumber = tempNumber / two;
          continue;
        }
        if (tempNumber.IsDivisibleByFive)
        {
          m_PrimeFactors.AddOne(ffive);
          tempNumber = tempNumber / five;
          continue;
        }
        if (tempNumber.IsDivisibleByThree)
        {
          m_PrimeFactors.AddOne(fthree);
          tempNumber = tempNumber / three;
          continue;
        }
        if (tempNumber.IsDivisibleByEleven)
        {
          m_PrimeFactors.AddOne(feleven);
          tempNumber = tempNumber / eleven;
          continue;
        }
        if (tempNumber.IsDivisibleBySeven)
        {
          m_PrimeFactors.AddOne(fseven);
          tempNumber = tempNumber / seven;
          continue;
        }
        break;
      }
      m_Remainder = new FastBigNumber(tempNumber.ToString());
    }

    /// <summary>
    /// Creates a full factorization for as much as it can (depends on the state of the PrimeGenerator)
    /// This implementation is in the naive way that tests all the previous primes
    /// I assume that simple factorization was already called so there is no need to initialize the remainder and the prime factors
    /// </summary>
    /// <param name="number">The number that we wish to factor</param>
    /// <param name="previousFactors">The previous factors computed (can be result of simple factorization)</param>
    /// <returns>The remainder of the factorization</returns>
    internal void CreateFullFactorization()
    {
      FactoringManager.Instance.ContinueCalculation(m_Remainder);
      FactoringManager.Instance.AllocateFactoringThread(this);
      
    }

    internal bool FullFactorization()
    {
      ForewardSkipListNode<FastBigNumber> node = FactoringManager.Instance.GetPrimesFirst();

      bool done = false;
      lock (m_FactoringLock)
      {
        done = m_Remainder.IsOne;
      }
      FastBigNumber prime;
      FastBigNumber mod;
      FastBigNumber tempRemainder;
      while (!done && node != null)
      {
        prime = node.Data;
        lock (m_FactoringLock)
          tempRemainder = new FastBigNumber(m_Remainder);
        mod = tempRemainder % prime;
        if (mod.IsZero)
        {
          lock (m_FactoringLock)
          {
            m_PrimeFactors.AddOne(prime);
            m_Remainder = m_Remainder / prime;
          }
        }
        lock (m_FactoringLock)
          done = m_Remainder.IsOne;
        node++;
      }

      return done;
    }
    #endregion

    #region Constructors
    public FactoringBigNumber()
    {
      m_Remainder = new FastBigNumber(0);
      m_PrimeFactors = new FactorsHashtable();
      m_IsNegative = false;
      SetFactorMode(FactorMode.None,false);
      //m_NonPrimeFactors = new FactorsHashtable();
    }

    public FactoringBigNumber(string number,FactorMode mode):this()
    {
      m_Remainder = new FastBigNumber(number);
      IsNegative = m_Remainder.IsNegative;
      m_Remainder.IsNegative = false;
      SetFactorMode(mode,false);
    }

    public FactoringBigNumber(string number)
      : this(number, FactorMode.Simple)
    { }

    private FactoringBigNumber(FactorsHashtable table, FastBigNumber remainder,FactorMode mode)
    {
      m_FactorMode = mode;
      m_IsNegative = remainder.IsNegative;
      FastBigNumber tempNumber = new FastBigNumber(remainder);
      tempNumber.IsNegative = false;
      CreateSimpleFactorization(tempNumber);
      m_PrimeFactors.Unify(table);
      if (mode == FactorMode.Full)
        CreateFullFactorization();
      
    }

    public FactoringBigNumber(FactoringBigNumber other)
    {
      lock (other.m_FactoringLock)
      {
        m_PrimeFactors = new FactorsHashtable();
        m_PrimeFactors.Unify(other.m_PrimeFactors);
        m_Remainder = new FastBigNumber(other.m_Remainder);
        IsNegative = other.IsNegative;
      }
    }
    #endregion

    /// <summary>
    /// Sets the factor mode for the number
    /// </summary>
    /// <param name="factorMode">The new factor mode</param>
    /// <param name="force">if true the new factor mode will be forced (for example when the inner remainder has been changed)</param>
    public void SetFactorMode(FactorMode factorMode, bool force)
    {
      if (!force && factorMode == m_FactorMode) return;
      switch (factorMode)
      {
        case FactorMode.None:
          m_Remainder = m_Remainder * m_PrimeFactors.ToFastBigNumber;
          m_PrimeFactors.Clear();
          break;
        case FactorMode.Simple:
          CreateSimpleFactorization(m_Remainder);
          break;
        case FactorMode.Full:
          CreateSimpleFactorization(m_Remainder);
          CreateFullFactorization();
          break;
        default:
          break;
      }
      m_FactorMode = factorMode;

    }

    #region Public Properties

    public FactorMode CurrentFactorMode
    {
      get
      {
        return m_FactorMode;
      }
    }

    public StdBigNumber ToStdBigNumber
    {
      get
      {
        FastBigNumber factors = null;
        lock (m_FactoringLock)
        {
          if (m_Remainder.IsZero)
            return new StdBigNumber(false);
        }
        lock (m_FactoringLock)
        {
          factors = m_PrimeFactors.ToFastBigNumber;
        }
        lock (m_FactoringLock)
        {
          FastBigNumber result = m_Remainder * factors;
          result.IsNegative = IsNegative;
          return result.ToStdBigNumber;
        }
      }
    }

    /// <summary>
    /// Gets the total number of factors for the number
    /// </summary>
    public int KnownFactorsCount
    {
      get
      {
        return m_PrimeFactors.KnownFactorsCount;
      }
    }

    public int DistinctFactorsCount
    {
      get
      {
        return m_PrimeFactors.Keys.Count;
      }
    }

    #endregion

    public void Initialize(string number)
    {
      m_Remainder = new FastBigNumber(number);
      IsNegative = m_Remainder.IsNegative;
      m_Remainder.IsNegative = false;
      SetFactorMode(FactorMode.Simple,true);
    }

    public void Negate()
    {
      IsNegative = !IsNegative;
    }

    public bool IsNegative
    {
      get { return m_IsNegative; }
      set
      {
        if (!IsZero)
          m_IsNegative = value;
      }
    }

    public int DigitCount
    {
      get { return ToStdBigNumber.DigitCount; }
    }

    public bool IsZero
    {
      get { return m_Remainder.IsZero; }
    }

    public bool IsOne
    {
      get 
      {
        return m_Remainder.IsOne && m_PrimeFactors.KnownFactorsCount == 0;
      }
    }


    #region Public Functions
    /// <summary>
    /// Returns the currently known factors and the remainder in a dictionary.
    /// </summary>
    /// <returns></returns>
    public Dictionary<FastBigNumber, int> Factors(out FastBigNumber remainder)
    {
      Dictionary<FastBigNumber, int> result = new Dictionary<FastBigNumber, int>();
      remainder = new FastBigNumber(m_Remainder);
      foreach (FastBigNumber key in m_PrimeFactors.Keys)
      {
        result.Add(key, m_PrimeFactors[key]);
      }
      return result;
    }
    #endregion
    
    public override string ToString()
    {
      return ToStdBigNumber.ToString();
    }

    /// <summary>
    /// Intersects two Factors tables and returns a factors table representing the intersection.
    /// </summary>
    /// <param name="table1"></param>
    /// <param name="table2"></param>
    /// <param name="remainder1"></param>
    /// <param name="remainder2"></param>
    /// <returns></returns>
    
    private static FactorsHashtable FactorsHashtableIntersect(FactorsHashtable table1, FactorsHashtable table2, ref FastBigNumber remainder1, ref FastBigNumber remainder2)
    {
      FactorsHashtable result = new FactorsHashtable();
      //remainder1 = new FastBigNumber("1");
      //remainder2 = new FastBigNumber("1");
      foreach (FastBigNumber key in table1.Keys)
      {
        int value1 = (int)table1[key];
        if (table2.ContainsKey(key))
        {
          int value2 = (int)table2[key];
          int min = Math.Min(value1, value2);
          result.Add(key, min);
          if (value1 == value2)
            continue;
          int delta = Math.Abs(value1 - value2);
          if (value1 > value2)
            remainder1 *= BigNumberMath.Power<FastBigNumber>(key, delta);
          else
            remainder2 *= BigNumberMath.Power<FastBigNumber>(key, delta);
        }
        else
        {
          remainder1 *= BigNumberMath.Power<FastBigNumber>(key, value1);
        }

      }
      foreach (FastBigNumber key in table2.Keys)
      {
        if (!table1.ContainsKey(key))
        {
          int value2 = (int)table2[key];
          remainder2 *= BigNumberMath.Power<FastBigNumber>(key, value2);
        }
      }
      return result;
    }

    #region Private Operator Implementation
    private static FactoringBigNumber Add(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      FastBigNumber remainder1 = null;
      FastBigNumber remainder2 = null;
      FactorsHashtable newFactors = null;
      lock (firstNumber.m_FactoringLock)
      {
        lock (secondNumber.m_FactoringLock)
        {
          remainder1 = new FastBigNumber(firstNumber.m_Remainder);
          remainder2 = new FastBigNumber(secondNumber.m_Remainder);
          newFactors = FactorsHashtableIntersect(firstNumber.m_PrimeFactors, secondNumber.m_PrimeFactors, ref remainder1, ref remainder2);
          remainder1.IsNegative = firstNumber.IsNegative;
          remainder2.IsNegative = secondNumber.IsNegative;
        }
      }
      FastBigNumber sum = remainder1 + remainder2;
      return new FactoringBigNumber(newFactors,sum,firstNumber.m_FactorMode);
    }

    private static FactoringBigNumber Subtract(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      FastBigNumber remainder1 = null;
      FastBigNumber remainder2 = null;
      FactorsHashtable newFactors = null;
      lock (firstNumber.m_FactoringLock)
      {
        lock (secondNumber.m_FactoringLock)
        {
          remainder1 = new FastBigNumber(firstNumber.m_Remainder);
          remainder2 = new FastBigNumber(secondNumber.m_Remainder);
          newFactors = FactorsHashtableIntersect(firstNumber.m_PrimeFactors, secondNumber.m_PrimeFactors, ref remainder1, ref remainder2);
          remainder1.IsNegative = firstNumber.IsNegative;
          remainder2.IsNegative = secondNumber.IsNegative;
        }
      }
      FastBigNumber sum = remainder1 - remainder2;
      return new FactoringBigNumber(newFactors, sum, firstNumber.m_FactorMode);
    }

    private static FactoringBigNumber Multiply(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      FastBigNumber tempNumber = null;
      FactorsHashtable tempTable = new FactorsHashtable();
      lock (firstNumber.m_FactoringLock)
      {
        lock (secondNumber.m_FactoringLock)
        {
          tempTable.Unify(firstNumber.m_PrimeFactors);
          tempTable.Unify(secondNumber.m_PrimeFactors);
          tempNumber = firstNumber.m_Remainder * secondNumber.m_Remainder;
          tempNumber.IsNegative = firstNumber.IsNegative ^ secondNumber.IsNegative;
        }
      }
      return new FactoringBigNumber(tempTable, tempNumber,firstNumber.m_FactorMode);
    }
    #endregion

    #region Operators
    public static FactoringBigNumber operator +(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      return Add(firstNumber, secondNumber);
    }

    public static FactoringBigNumber operator -(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      return Subtract(firstNumber, secondNumber);
    }

    public static FactoringBigNumber operator *(FactoringBigNumber firstNumber, FactoringBigNumber secondNumber)
    {
      return Multiply(firstNumber, secondNumber);
    }
    #endregion

    #region IComparable<FactoringBigNumber> Members

    int IComparable<FactoringBigNumber>.CompareTo(FactoringBigNumber other)
    {
      throw new NotImplementedException();
    }

    #endregion

    #region IBigNumber Members


    public IBigNumber IAdd(IBigNumber second)
    {
      FactoringBigNumber sSecond = second as FactoringBigNumber;
      return this + sSecond;
    }

    public IBigNumber ISub(IBigNumber second)
    {
      FactoringBigNumber sSecond = second as FactoringBigNumber;
      return this - sSecond;
    }

    public IBigNumber IMul(IBigNumber second)
    {
      FactoringBigNumber sSecond = second as FactoringBigNumber;
      return this * sSecond;
    }

    public IBigNumber IDiv(IBigNumber second)
    {
      throw new NotImplementedException();
    }

    public IBigNumber IMod(IBigNumber second)
    {
      throw new NotImplementedException();
    }

    public IBigNumber IClone()
    {
      return new FactoringBigNumber(this);
    }

    public IBigNumber IConstruct(string number)
    {
      return new FactoringBigNumber(number);
    }

    public void IAbs()
    {
      IsNegative = false;
    }

    public bool IEqual(IBigNumber second)
    {
      return this == (second as FactoringBigNumber);
    }

    public bool ISmaller(IBigNumber second)
    {
      throw new NotImplementedException();
      //return this < (second as FactoringBigNumber);
    }
    #endregion
  }
}
